package com.leetcode.dfs;

import java.util.*;

public class Leetcode51 {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        String[][] path = new String[n][n];
        for (int i = 0; i < path.length; i++) {
            Arrays.fill(path[i], ".");
        }
        dfs(path, 0);
        return res;
    }

    private void dfs(String[][] path, int row) {
        if (row == path.length) {
            res.add(arrToStr(path));
            return;
        }

        for (int col = 0; col < path.length; col++) {
            // 判断row col 是否合法
            if (!isValid(path, row, col)) {
                continue;
            }
            path[row][col] = "Q";
            dfs(path, row + 1);
            path[row][col] = ".";
        }

    }

    private boolean isValid(String[][] path, int row, int col) {
        int n = path.length;

        // 判断当前列
        for (int i = 0; i < row; i++) {
            if (("Q").equals(path[i][col])) {
                return false;
            }
        }

        // 判断左上
        for (int i = row - 1, j = col - 1 ;i >= 0 && j >= 0; i--, j--) {
            if ("Q".equals(path[i][j])) {
                return false;
            }
        }

        // 判断右上
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i-- , j++) {
            if ("Q".equals(path[i][j])) {
                return false;
            }
        }
        return true;
    }

    private List<String> arrToStr(String[][] path) {
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < path.length; i++) {
            String s = "";
            for (int j = 0; j < path[i].length; j++) {
                s += path[i][j];
            }
            ans.add(s);
        }
        return ans;
    }

    public static void main(String[] args) {
        Leetcode51 leetcode51 = new Leetcode51();
        List<List<String>> ans = leetcode51.solveNQueens(4);
        System.out.println(ans);
    }
}
